package tree;

import java.util.ArrayList;

/**
 * 给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。
 * 由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。
 * <p>
 * 示例 1：
 * 输入：root = [1,2,3,4,5,6]
 * 输出：110
 * 解释：删除红色的边，得到 2 棵子树，和分别为 11 和 10 。它们的乘积是 110 （11*10）
 * <p>
 * 示例 2：
 * 输入：root = [1,null,2,3,4,null,null,5,6]
 * 输出：90
 * 解释：移除红色的边，得到 2 棵子树，和分别是 15 和 6 。它们的乘积为 90 （15*6）
 * <p>
 * 示例 3：
 * 输入：root = [2,3,9,10,7,8,6,5,4,11,1]
 * 输出：1025
 * <p>
 * 示例 4：
 * 输入：root = [1,1]
 * 输出：1
 *
 * @author Jisheng Huang
 * @version 20250424
 */
public class MaxProdOfSplittedBT_1339 {
    public static ArrayList<Integer> res = new ArrayList<>();
    public static int sum;
    public static int best;

    /**
     * Using preorder and postorder to find the maximum
     *
     * @param root the given root node of a binary tree
     * @return the maximum product when removing one edge
     */
    public static int maxProduct(TreeNode root) {
        preOrder(root);
        postOrder(root);

        return (int) (((long) best * (sum - best)) % 1000000007);
    }

    private static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        sum += root.val;
        preOrder(root.left);
        preOrder(root.right);
    }

    private static int postOrder(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int cur = postOrder(root.left) + postOrder(root.right) + root.val;

        if (Math.abs(2 * cur - sum) < Math.abs(2 * best - sum)) {
            best = cur;
        }

        return cur;
    }


    /**
     * Private TreeNode class
     */
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
